package Ali;

import java.util.*;

/**
 * @author le
 */
public class Test01
{
    public static void main(String[] args)
    {
        // 待排序的数组
        int[] nums = {9,8,7,6,5,4,3,2,1};
        int[] res = new int[nums.length];

        mergeSort(nums,0,nums.length-1,res);

        for (int i = 0; i < nums.length; i++)
        {
            System.out.println(nums[i]);
        }

    }

    public static void merge(int[] arr,int low,int mid,int high,int[] temp){
        int index = 0;
        int i = low;
        int j = mid+1;

        while(i <= mid && j<= high){
            temp[index++] = arr[i] > arr[j]?arr[j++]:arr[i++];
        }

        while(i <= mid){
            temp[index++] = arr[i++];
        }

        while(j <= high){
            temp[index++] = arr[j++];
        }

        for (int t = 0;t < index;t++){
            arr[low+t] = temp[t];
        }
    }


    public static void mergeSort(int[] arr,int low,int high,int[] temp){
        if (low < high){
            int mid = (high + low)/2;
            mergeSort(arr,0,mid,temp);
            mergeSort(arr,mid+1,high,temp);
            merge(arr,low,mid,high,temp);
        }
    }

}
